package org.example.method;

import org.example.graph.Edge;
import org.example.graph.Vertex;

import java.util.ArrayList;
import java.util.List;

/**
 * <h3>Bellman-Ford 算法，可以处理负边</h3>
 */
public class BellmanFord {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.edges = List.of(new Edge(v2,2),
                new Edge(v3,1));

        v2.edges = List.of(new Edge(v3,-2));
        v3.edges = List.of(new Edge(v4,1));
        v4.edges = List.of();
        List<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4));

        bellmanFord(graph, v1);

        for (Vertex vertex : graph) {
            System.out.println(vertex.getName() +" "+vertex.dist);
            System.out.println(vertex.path.toString());
        }
    }

    private static void bellmanFord(List<Vertex> graph, Vertex vertex) {
        vertex.dist = 0;
        for (int i = 0; i < graph.size() - 1; i++) {
            for (Vertex s : graph) {
                for (Edge linked : s.edges) {
                    Vertex e = linked.linked;
                    if (s.dist != Integer.MAX_VALUE && (s.dist + linked.weight) < e.dist){
                        e.dist = s.dist + linked.weight;
                        e.path = new ArrayList<>(s.path);
                        e.path.add(s.getName());
                    }
                }
            }
        }
        
    }

}
